/*
 * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
 * Copyright (c) 1995 Martin Husemann
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    This product includes software developed by Martin Husemann
 *    and Wolfgang Solfrank.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/cdefs.h>
#include <assert.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdio.h>
#include <unistd.h>
#include "fsck_tree.h"
#include "fstool_common.h"
#include "fstool_io.h"
#include "fsck_fragment.h"
#include "fsck_cache.h"
#include "fsck_fat.h"

/** Global variables **/
static FSCK_FRAGMENT_S *s_pstLastFreeFrag= NULL;
static FSCK_FRAGMENT_S *s_pstLastBadFrag= NULL;
static unsigned int *s_pszFatBitMap=NULL;

//clusetr 2-->3-->......->pstBoot->NumClusters -1
int FAT_IsValidCluster(FSCK_BOOT_SECTOR_S* pstBoot, cl_t cl)
{
    if ((FSTOOL_COMM_CLUSTER_FIRST <= cl) && (pstBoot->NumClusters > cl))
    {
        return 1;
    }

    return 0;
}

int FAT_IsAllocatedCluster(cl_t cl)
{
    if ((FSTOOL_COMM_CLUSTER_FREE == cl) || (FSTOOL_COMM_CLUSTER_RSRVD >= cl))
    {
        return 0;
    }

    return 1;
}

int FAT_IsEOFCluster(cl_t cl)
{
    if ((FSTOOL_COMM_CLUSTER_EOFS > cl) || (FSTOOL_COMM_CLUSTER_EOF < cl))
    {
        return 0;
    }

    return 1;
}

int FAT_IsBadCluster(cl_t cl)
{
    if (FSTOOL_COMM_CLUSTER_BAD == cl)
    {
        return 1;
    }

    return 0;
}

int FAT_IsRsrvCluster(cl_t cl)
{
    if (FSTOOL_COMM_CLUSTER_RSRVD == cl)
    {
        return 1;
    }

    return 0;
}

int FAT_IsFreeCluster(cl_t cl)
{
    if (FSTOOL_COMM_CLUSTER_FREE == cl)
    {
        return 1;
    }

    return 0;
}

int FAT_IsCircularChain(cl_t curCl, cl_t nextCl)
{
    if (curCl == nextCl)
    {
        return 1;
    }

    return 0;
}

static int FAT_CheckCluster(FSCK_BOOT_SECTOR_S* pstBoot, cl_t cur, cl_t next)
{
    struct FSCK_FRAGMENT_S *frag = NULL;
    struct FSCK_FRAGMENT_S *insert = NULL;
    if (FAT_IsEOFCluster(next))
    {
        return FSCK_FSOK;
    }
    else if (FAT_IsFreeCluster(next))
    {
        /**update free cluster tree,if the cur(next is 0) is free and cur cl is isolated*/
        pstBoot->NumFree++;
        if (s_pstLastFreeFrag)
        {
            if ( cur == (s_pstLastFreeFrag->head + s_pstLastFreeFrag->length))
            {
                s_pstLastFreeFrag->length  += 1;
                return FSCK_FSOK;
            }
        }
        frag = FSCK_FRAGMENT_New();
        if(!frag)
        {
            FSTOOL_COMM_LOG_ERROR("No space \n");
            return FSCK_FSFATAL|FSCK_OOM;
        }
        frag->head = cur;
        frag->length = 1;
        insert = FSCK_FRAGMENT_Insert(&g_stFreeCluster, frag);
        if (insert)
        {
            FSTOOL_COMM_LOG_ERROR("%s:FSCK_FRAGMENT_S(head:0x%x) exist\n",__func__,frag->head);
            free(frag);
            return FSCK_FSFATAL;
        }
        s_pstLastFreeFrag = frag;
        return FSCK_FSOK;
    }
    else if (FAT_IsBadCluster(next))
    {
        //update bad cluster tree
        pstBoot->NumBad++;
        if (s_pstLastBadFrag)
        {
            if (cur == (s_pstLastBadFrag->head + s_pstLastBadFrag->length))
            {
                s_pstLastBadFrag->length  += 1;
                return FSCK_FSOK;
            }
        }
        frag = FSCK_FRAGMENT_New();
        if(!frag)
        {
            FSTOOL_COMM_LOG_ERROR("No Space\n");
            return FSCK_FSFATAL|FSCK_OOM;
        }
        frag->head = cur;
        frag->length = 1;

        insert = FSCK_FRAGMENT_Insert(&g_stBadCluster, frag);
        if (insert)
        {
            FSTOOL_COMM_LOG_ERROR("%s:FSCK_FRAGMENT_S(head:0x%x) exist\n",__func__,frag->head);
            free(frag);
            return FSCK_FSFATAL;
        }
        s_pstLastBadFrag = frag;
        return FSCK_FSOK;
    }

    return FSCK_FSOK;
}

static int FAT_CheckDifferCluster(FSCK_BOOT_SECTOR_S* pstBoot, cl_t cl, cl_t mainCl, cl_t backCl, int bakFATNo, int* pDestFatNo)
{
    int mainFATNo = 0;

    FSTOOL_COMM_LOG_WARN("[Cluster:%u] is marked different as [FAT0:%u, FAT%d:%u]\n", cl, mainCl, bakFATNo, backCl);
    if (FAT_IsValidCluster(pstBoot, mainCl) || FAT_IsEOFCluster(mainCl))
    {
        *pDestFatNo = mainFATNo;
    }
    else
    {
        if (FAT_IsValidCluster(pstBoot, backCl) || FAT_IsEOFCluster(backCl))
        {
            *pDestFatNo = bakFATNo;
        }
        else
        {
            *pDestFatNo = mainFATNo;
        }
    }

    return FSCK_FSFATMOD;
}

u_int FSCK_FAT_Read(int fs, FSCK_BOOT_SECTOR_S *pstBoot, int fatNo, u_char **buffer)
{
    loff_t off = 0;
    size_t fatSize = (size_t)pstBoot->BPB_FATSz32 * pstBoot->BPB_BytesPerSec;
    FSTOOL_COMM_LOG_INFO("Attempting to allocate %u KB for FAT\n", (u_int)(fatSize / FSTOOL_COMM_KB_2_BYTE_FACTOR));

    *buffer = malloc(fatSize);
    if (NULL == *buffer)
    {
        FSTOOL_COMM_LOG_ERROR("%s:Read fat failed due to malloc failed.\n", __func__);
        return FSCK_FSFATAL|FSCK_OOM;
    }

    if (0 >= fatNo)
    {
        fatNo = 0;
    }

    off = (loff_t)pstBoot->BPB_RsvdSecCnt + fatNo * pstBoot->BPB_FATSz32;   /*lint !e647*/
    if (FSCK_FSOK != FSTOOL_IO_Read(fs, off, pstBoot->BPB_FATSz32, *buffer))
    {
        FSTOOL_COMM_LOG_ERROR("%s:Read fat failed\n", __func__);
        free(*buffer);
        *buffer = NULL;
        return FSCK_FSFATAL|FSCK_READERR;
    }

    return FSCK_FSOK;
}

/*-
 * The first 2 FAT entries contain pseudo-cluster numbers with the following
 * layout:
 *
 * 31...... ........ ........ .......0
 * rrrr1111 11111111 11111111 mmmmmmmm  FAT32 entry 0
 * rrrrsh11 11111111 11111111 11111xxx          FAT32 entry 1
 * r = reserved
 * m = BPB media ID byte
 * s = clean flag (1 = dismounted; 0 = still mounted)
 * h = hard error flag (1 = ok; 0 = I/O error)
 * x = any value ok
 * return 1 dirty, 0 clean
 */

int FSCK_FAT_IsDirty(FSCK_BOOT_SECTOR_S *pstBoot, u_char* fat)
{
    /*If not in line with fat file system,assumed to be unclean.*/
    if (fat[0] != pstBoot->BPB_Media || fat[1] != 0xff
        ||fat[2] != 0xff || (fat[3] & 0x0f) != 0x0f
        || (fat[4] & 0xf8) != 0xf8 || fat[5] != 0xff
        || fat[6] != 0xff || (fat[7] & 0x0f) != 0x0f)
    {
        FSTOOL_COMM_LOG_WARN("File system is dirty due to fat[0,1]!\n");
        return 1;
    }

    return 0;
}

u_int FSCK_FAT_CleanDirtyFlag(FSCK_BOOT_SECTOR_S* pstBoot, int fd)
{
    u_char buffer[8] = {0};
    u_char sector_buffer[FSCK_BOOT_MAX_BLOCK_SIZE];
    unsigned int i = 0, j = 0;
    loff_t off = 0;
    u_int ret = FSCK_FSOK;

    buffer[0] = (u_char)pstBoot->BPB_Media;
    buffer[1] = 0xff;
    buffer[2] = 0xff;
    buffer[3] = 0x0f;
    buffer[4] = 0xff;
    buffer[5] = 0xff;
    buffer[6] = 0xff;
    buffer[7] = 0x0f;

    for (i = 0; i < pstBoot->BPB_NumFATs; i++)
    {
        off = (loff_t)pstBoot->BPB_RsvdSecCnt + i * pstBoot->BPB_FATSz32;   /*lint !e647*/

        if (FSCK_FSOK != FSTOOL_IO_Read(fd, off, 1, sector_buffer))
        {
            FSTOOL_COMM_LOG_ERROR("Unable to read fat dirty flag sector\n");
            ret = FSCK_FSFATAL|FSCK_WRITERR;
            continue;
        }

        for(j = 0; j < 8; j++)
        {
            sector_buffer[j] = buffer[j];
        }

        if (FSCK_FSOK != FSTOOL_IO_Write(fd, off, 1, sector_buffer))
        {
            FSTOOL_COMM_LOG_ERROR("Unable to write fat dirty flag\n");
            ret = FSCK_FSFATAL|FSCK_WRITERR;
        }
    }

    return ret;
}

u_int FSCK_FAT_Cmp(FSCK_BOOT_SECTOR_S *pstBoot, u_char*first, u_char  *second, int fatNo)
{
    cl_t cl = 0;
    u_char *sp = NULL;
    u_char *fp = NULL;
    u_char *wp = NULL;
    u_int ret = FSCK_FSOK;
    int destFATNo = 0;
    cl_t first_cl = 0;
    cl_t second_cl = 0;
    cl_t w_cl = 0;
    FSTOOL_COMM_LOG_INFO("Begin to compare FAT ! \n");

    for (cl = FSTOOL_COMM_CLUSTER_FIRST; cl < pstBoot->NumClusters; cl++)
    {
        fp = first + 4*cl;
        sp = second + 4*cl;
        first_cl = (fp[0] + (fp[1]<<8) + (fp[2]<<16) + (fp[3]<<24)) & pstBoot->FATClustMask;
        second_cl = (sp[0] + (sp[1]<<8) + (sp[2]<<16) + (sp[3]<<24)) & pstBoot->FATClustMask;

        if (first_cl == second_cl)
        {
            continue;
        }

        ret |= FAT_CheckDifferCluster(pstBoot, cl, first_cl, second_cl, fatNo, &destFATNo);
        if (destFATNo)
        {
            wp = fp;
            w_cl = second_cl;
        }else
        {
            wp = sp;
            w_cl = first_cl;
        }
        /* fisrt_cl = second_cl */
        *wp++ = (u_char)w_cl;
        *wp++ = (u_char)(w_cl >>8);
        *wp++ = (u_char)(w_cl >> 16);
        *wp &= 0xf0;
        *wp |= (w_cl >>24) &0x0f;
    }
    return ret;
}

 /*lint -e665 -e504 -e534 -e613 -e438*/
u_int FSCK_FAT_Check(FSCK_BOOT_SECTOR_S* pstBoot, int fatNo, u_char *buffer)
{
    FSCK_CACHE_CLUSTER_CHAIN_S* pstCurChain  = NULL;
    FSCK_CACHE_CLUSTER_CHAIN_S* pstPrevChain = NULL;
    FSCK_CACHE_CLUSTER_CHAIN_S* insert = NULL;
    FSCK_CACHE_CLUSTER_CHAIN_S stChainToFind= {0};
    FSCK_CACHE_S* pstCache = NULL;
    u_char* p = NULL;
    cl_t cl = 0;
    cl_t curcl = 0;
    cl_t nextcl = 0;
    cl_t next2nextcl = 0;
    int len = 0;
    u_int ret = FSCK_FSOK;
    u_int err = 0;

    pstBoot->NumFree = pstBoot->NumBad = 0;
    if (fatNo<0)
    {
        fatNo=0;
    }

    s_pszFatBitMap = calloc((size_t)(pstBoot->NumClusters/32+1),sizeof(unsigned int));
    if(!s_pszFatBitMap)
    {
        FSTOOL_COMM_LOG_ERROR("NO space left\n");
        return FSCK_FSFATAL|FSCK_OOM;
    }

    FSTOOL_COMM_LOG_INFO("Begin to handle the cluster chain! \n");

    for (cl = FSTOOL_COMM_CLUSTER_FIRST; cl < pstBoot->NumClusters;cl++)
    {
        if (FSCK_BIT(s_pszFatBitMap[cl/32],cl%32))
        {
            continue;
        }

        curcl = nextcl = cl;
        len = 0;
        p = buffer + 4*cl;
        while (FAT_IsValidCluster(pstBoot, nextcl))
        {
            curcl = nextcl;
            nextcl = p[0] + (p[1] << 8) + (p[2] << 16) + (p[3] << 24);

            ret|= err = FAT_CheckCluster(pstBoot,curcl, nextcl);
            if (err & FSCK_FSFATAL)
            {
                FSTOOL_COMM_LOG_ERROR("FatCheckCluster error !\n");
                return err;
            }

            len++;
            if (1 == len)
            {
                if (FAT_IsFreeCluster(nextcl) || FAT_IsBadCluster(nextcl))
                {
                    //curcl will not in any cluster chain
                    SET_BIT(s_pszFatBitMap[curcl/32],curcl%32);
                    break;
                }
                else if (!(FAT_IsValidCluster(pstBoot, nextcl) || FAT_IsEOFCluster(nextcl)))
                {
                    FSTOOL_COMM_LOG_WARN("Clusters chain starting with invalid cluster(%u), setting to EOF !\n",nextcl);
                    nextcl = FSTOOL_COMM_CLUSTER_EOF;
                    ret |= FSCK_FSFATMOD;
                }
                else if (FAT_IsCircularChain(curcl, nextcl))
                {
                    FSTOOL_COMM_LOG_WARN("Clusters chain[head:%u, curcl:%u, nextcl:%u] form a circle, setting curcl(%u) to EOF !\n",cl, curcl, nextcl, curcl);
                    nextcl = FSTOOL_COMM_CLUSTER_EOF;
                    ret |= FSCK_FSFATMOD;
                }
            }
            else
            {
                //curcl has been insert to the chain in last loop, and if the nextcl is same to the head of chain, curcl will be EOF
                if (FAT_IsEOFCluster(nextcl))
                {
                    SET_BIT(s_pszFatBitMap[curcl/32],curcl%32);
                    break;
                }
                else if (!FAT_IsValidCluster(pstBoot, nextcl))
                {
                    FSTOOL_COMM_LOG_WARN("Clusters chain starting at %u ends with invalid cluster(%u-->%u), setting cluster(%u) to EOF !\n",cl,curcl,nextcl,curcl);
                    SET_BIT(s_pszFatBitMap[curcl/32],curcl%32);
                    ret |= FSCK_FSFATMOD;
                    break;
                }
                else if (FAT_IsCircularChain(curcl, nextcl))
                {
                    FSTOOL_COMM_LOG_WARN("[head:%u, curcl:%u, nextcl:%u] form a circle, and [curcl:%u] will be set EOF\n", cl, curcl, nextcl, curcl);
                    SET_BIT(s_pszFatBitMap[curcl/32],curcl%32);
                    ret |= FSCK_FSFATMOD;
                    break;
                }
            }

            if (FAT_IsValidCluster(pstBoot, nextcl))
            {
                p = buffer + 4*nextcl;
                next2nextcl = p[0] + (p[1] << 8) + (p[2] << 16) + (p[3] << 24);
                if (FAT_IsBadCluster(next2nextcl) || FAT_IsFreeCluster(next2nextcl))
                {
                    FSTOOL_COMM_LOG_WARN("Clusters chain starting at (%u) ends with bad or free cluster(%u), setting prev cluster(%u) to EOF !\n", cl,nextcl,curcl);

                    ret |= FSCK_FSFATMOD;

                    if (1 == len)
                    {
                        nextcl = FSTOOL_COMM_CLUSTER_EOF;
                    }
                    else
                    {
                        //curcl has been insert to the chain in last loop, and if the nextcl is bad, curcl will be EOF
                        SET_BIT(s_pszFatBitMap[curcl/32],curcl%32);
                        break;
                    }
                }
            }

            //two chain with one cluster
            if (FAT_IsValidCluster(pstBoot, nextcl) && FSCK_BIT(s_pszFatBitMap[nextcl/32],nextcl%32))
            {
                SET_BIT(s_pszFatBitMap[curcl/32],curcl%32);
                stChainToFind.head = nextcl;
                pstPrevChain = FSCK_CACHE_FindChain(&g_stAllocatedCluster, &stChainToFind);
                if (pstPrevChain && (pstPrevChain != pstCurChain))
                {
                    /**it is case,because 0x3->0x34->0x35->EOF,then you find 0x100->0x3.*/
                    if (1 == len)
                    {
                        pstCurChain = FSCK_CACHE_NewChain();
                        if(!pstCurChain)
                        {
                            FSTOOL_COMM_LOG_ERROR("FSCK_CACHE_NewChain error \n");
                            return FSCK_FSFATAL|FSCK_OOM;
                        }
                        pstCurChain->head = curcl;
                        pstCurChain->length = 1;

                        insert = FSCK_CACHE_InsertChain(&g_stAllocatedCluster, pstCurChain);
                        if (insert)
                        {
                            FSTOOL_COMM_LOG_ERROR("%s:fatentry(head:0x%x) exist\n",__func__,pstCurChain->head);
                            return FSCK_FSFATAL;
                        }

                        pstCache = FSCK_CACHE_New();
                        if(!pstCache)
                        {
                            FSTOOL_COMM_LOG_ERROR("FSCK_CACHE_New error \n");
                            return FSCK_FSFATAL|FSCK_OOM;
                        }
                        pstCache->head = curcl;
                        pstCache->length = 1;
                        FSCK_CACHE_Add(pstCurChain,pstCache);
                        pstCache->next = pstPrevChain->child;
                        pstCurChain->length += pstPrevChain->length;
                    }
                    else
                    {
                        FSCK_CACHE_AddToTail(pstCurChain,pstPrevChain->child);
                        pstCurChain->length += pstPrevChain->length;
                    }
                    pstPrevChain->child = NULL;
                    FSCK_CACHE_RemoveChain(&g_stAllocatedCluster, pstPrevChain);
                    free(pstPrevChain);
                    pstPrevChain = NULL;
                    break;
                }
                else
                {
                    FSTOOL_COMM_LOG_WARN("Cluster chain[head:%u, curcl:%u, nextcl:%u] has same cluster with another chain, set curcl(%u) to EOF.\n", cl, curcl, nextcl, curcl);
                    FSCK_CACHE_DumpChain(pstCurChain);
                    FSCK_CACHE_DumpChain(pstPrevChain);
                    if(!pstCurChain)
                    {
                        break;
                    }

                    ret |= FSCK_FSFATMOD;
                    break;
                }
            }

            SET_BIT(s_pszFatBitMap[curcl/32],curcl%32);

            if (1 == len)
            {
                pstCurChain = FSCK_CACHE_NewChain();
                if(!pstCurChain)
                {
                    FSTOOL_COMM_LOG_ERROR("No space \n");
                    return FSCK_FSFATAL|FSCK_OOM;
                }
                pstCurChain->head = cl;
                insert = FSCK_CACHE_InsertChain(&g_stAllocatedCluster, pstCurChain);
                if (insert)
                {
                    FSTOOL_COMM_LOG_ERROR("%s:fatentry(head:0x%x) exist\n",__func__,pstCurChain->head);
                    free(pstCurChain);
                    pstCurChain = NULL;
                    return FSCK_FSFATAL;
                }

                pstCache = FSCK_CACHE_New();
                if(!pstCache)
                {
                    FSTOOL_COMM_LOG_ERROR("No space \n");
                    free(pstCurChain);
                    pstCurChain = NULL;
                    return FSCK_FSFATAL|FSCK_OOM;
                }
                pstCache->head = curcl;
                pstCache->length = 1;
                FSCK_CACHE_Add(pstCurChain,pstCache);

                //if curcl is EOF, just break, and this chain is only one cluster
                if (FAT_IsEOFCluster(nextcl))
                {
                    break;
                }
            }

            //curcl has been insert to this chain in last loop
            if (curcl + 1 == nextcl)
            {
                pstCache->length += 1;
                pstCurChain->length += 1;
            }
            else
            {
                pstCache = FSCK_CACHE_New();
                if(!pstCache)
                {
                    FSTOOL_COMM_LOG_ERROR("No Space\n");
                    return FSCK_FSFATAL|FSCK_OOM;
                }
                pstCurChain->segments+=1;
                pstCache->head = nextcl;
                pstCache->length = 1;
                FSCK_CACHE_Add(pstCurChain,pstCache);//pstCurChain->length has Lengthen in FSCK_CACHE_Add
            }

            //here nextcl has been add to this chain
        }

        pstCurChain = NULL;
    }

    if (s_pszFatBitMap)
    {
        free(s_pszFatBitMap);
        s_pszFatBitMap = NULL;
    }

    return ret;
}
 /*lint +e665 +e504 +e534 +e613 +e438*/

void FSCK_FAT_ClearChain(FSCK_BOOT_SECTOR_S *pstBoot, FSCK_CACHE_CLUSTER_CHAIN_S *fat)
 {
    struct FSCK_CACHE_S *curr = NULL;
    struct FSCK_CACHE_S *next = NULL;
    struct FSCK_FRAGMENT_S *frag = NULL;
    struct FSCK_FRAGMENT_S *insert = NULL;

    pstBoot->NumFree += fat->length;
    curr = fat->child;
    while (curr)
    {
        next = curr->next;
        frag = FSCK_FRAGMENT_New();
        if(!frag)
        {
            FSTOOL_COMM_LOG_WARN("%s: No space left\n",__func__);
            goto freeMemory;
        }
        frag->head = curr->head;
        frag->length = curr->length;

        insert = FSCK_FRAGMENT_Insert(&g_stFreeCluster, frag);
        if (insert)
        {
            FSTOOL_COMM_LOG_WARN("%s:FSCK_FRAGMENT_S(head:0x%x) exist\n",__func__,frag->head);
            free(frag);
            frag = NULL;
        }
freeMemory:
        free(curr);
        curr = next;
    }
    FSCK_CACHE_RemoveChain(&g_stAllocatedCluster, fat);
    free(fat);
}

u_int FSCK_FAT_Write(int fs, FSCK_BOOT_SECTOR_S *pstBoot)
{
    u_char *buffer = NULL;
    u_char *p = NULL;
    cl_t cl = 0;
    unsigned int i = 0;
    size_t szFat = 0;
    loff_t off = 0;
    u_int ret = FSCK_FSOK;
    struct FSCK_CACHE_CLUSTER_CHAIN_S *pstChain = NULL;
    struct FSCK_CACHE_S *pstCache = NULL;
    struct FSCK_FRAGMENT_S *pstFrag = NULL;

    szFat = (size_t)pstBoot->BPB_FATSz32 * pstBoot->BPB_BytesPerSec;
    buffer = malloc(szFat);
    if (NULL == buffer)
    {
        FSTOOL_COMM_LOG_ERROR("No space for FAT");
        return FSCK_FSFATAL|FSCK_OOM;
    }
    (void)memset_s(buffer, szFat, 0x00, szFat);
    p = buffer;

    *p++ = (u_char)pstBoot->BPB_Media;
    *p++ = 0xff;
    *p++ = 0xff;
    *p++ = 0x0f;
    *p++ = 0xff;
    *p++ = 0xff;
    *p++ = 0xff;
    *p++ = 0x0f;

    FSTOOL_COMM_LOG_INFO("begin to write FAT\n");
    pstChain = FSCK_CACHE_MinChain(&g_stAllocatedCluster);
    if(!pstChain)
    {
        FSTOOL_COMM_LOG_ERROR("%s:Allocated cluster tree is empty\n",__func__);
        free(buffer);
        return FSCK_FSFATAL;
    }

    FSTOOL_COMM_LOG_INFO("set valid cluster chain\n");
    while (pstChain)
    {
        pstCache = pstChain->child;
        while (pstCache)
        {
            cl = pstCache->head;
            for( i = 0 ; i < (pstCache->length - 1);i++)
            {
                FSCK_CACHE_SetNext(buffer,cl+i ,cl+i+1);
            }

            if (pstCache->next)
            {
                FSCK_CACHE_SetNext(buffer,cl+pstCache->length -1,pstCache->next->head);
            }
            else
            {
                FSCK_CACHE_SetNext(buffer,cl+pstCache->length -1,FSTOOL_COMM_CLUSTER_EOF);
            }
            pstCache = pstCache->next;
        }
        pstChain = FSCK_CACHE_NextChain(pstChain);
    }

    FSTOOL_COMM_LOG_INFO("set free cluster\n");
    for (pstFrag = FSCK_FRAGMENT_Min(&g_stFreeCluster); NULL != pstFrag; pstFrag = FSCK_FRAGMENT_Next(pstFrag))
    {
        cl = pstFrag->head;
        for(i = 0 ; i < pstFrag->length ;i++)
        {
            FSCK_CACHE_SetNext(buffer,cl+i ,FSTOOL_COMM_CLUSTER_FREE);
        }
    }

    FSTOOL_COMM_LOG_INFO("set bad cluster\n");
    for (pstFrag = FSCK_FRAGMENT_Min(&g_stBadCluster); NULL != pstFrag; pstFrag = FSCK_FRAGMENT_Next(pstFrag))
    {
        cl = pstFrag->head;
        for(i = 0 ; i < pstFrag->length ;i++)
        {
            FSCK_CACHE_SetNext(buffer,cl+i ,FSTOOL_COMM_CLUSTER_BAD);
        }
    }

    for (i = 0; i < pstBoot->BPB_NumFATs; i++)
    {
        FSTOOL_COMM_LOG_DEBUG("write FAT%u \n",i);
        off = (loff_t)pstBoot->BPB_RsvdSecCnt + i * pstBoot->BPB_FATSz32;   /*lint !e647*/
        if (FSCK_FSOK != FSTOOL_IO_Write(fs, off, pstBoot->BPB_FATSz32, buffer))
        {
            FSTOOL_COMM_LOG_ERROR("Unable to write FAT");
            ret = FSCK_FSFATAL|FSCK_WRITERR;
        }
    }

    free(buffer);
    return ret;
}

u_int FSCK_FAT_CheckLost(FSCK_BOOT_SECTOR_S* pstBoot)
{
    u_int mod = FSCK_FSOK;
    struct FSCK_CACHE_CLUSTER_CHAIN_S* pstChain = NULL;
    struct FSCK_CACHE_CLUSTER_CHAIN_S* pstNextChain = NULL;
    pstChain = FSCK_CACHE_MinChain(&g_stAllocatedCluster);
    if(!pstChain)
    {
        FSTOOL_COMM_LOG_ERROR("%s:g_stAllocatedCluster tree is empty\n",__func__);
        return FSCK_FSFATAL;
    }

    while (pstChain)
    {
        if (pstChain->flag & FSTOOL_COMM_CLUSTER_CHAIN_USED)
        {
            pstChain = FSCK_CACHE_NextChain(pstChain);
            continue;
        }
        FSTOOL_COMM_LOG_INFO("Lost cluster chain at head %u ,%d Cluster(s) lost\n",pstChain->head, pstChain->length);
        pstNextChain = FSCK_CACHE_NextChain(pstChain);
        FSCK_FAT_ClearChain(pstBoot, pstChain);
        mod |= FSCK_FSFATMOD;
        pstChain = pstNextChain;
    }

    return mod;
}

u_int FSCK_FAT_GetLastAlloCl(FSCK_BOOT_SECTOR_S *pstBoot, cl_t* pLastAllocCl)
{
    cl_t tmpCl = 0;
    cl_t lastCl = 0;
    FSCK_CACHE_CLUSTER_CHAIN_S* pstCurChain = NULL;
    FSCK_CACHE_S* pstCurCache = NULL;

    pstCurChain = FSCK_CACHE_MinChain(&g_stAllocatedCluster);
    if(!pstCurChain)
    {
        FSTOOL_COMM_LOG_ERROR("%s:Allocated cluster tree is empty\n",__func__);
        return FSCK_FSFATAL;
    }

    while (pstCurChain)
    {
        pstCurCache = pstCurChain->child;
        while (pstCurCache)
        {
            tmpCl = pstCurCache->head + pstCurCache->length - 1;
            if (lastCl < tmpCl)
            {
                lastCl = tmpCl;
            }
            pstCurCache = pstCurCache->next;
        }
        pstCurChain = FSCK_CACHE_NextChain(pstCurChain);
    }

    if (lastCl > pstBoot->NumClusters || lastCl < FSTOOL_COMM_CLUSTER_FIRST)
    {
        *pLastAllocCl = FSTOOL_COMM_CLUSTER_FIRST;
    }
    else
    {
        *pLastAllocCl = lastCl;
    }

    return FSCK_FSOK;
}

u_int FSCK_FAT_CheckFragment(unsigned int u32FragmentThr)
{
    unsigned int uUesdChainCnt=0;
    unsigned int uUsedSegmentCnt=0;
    unsigned int uFreeSegmentCnt=0;
    float fVlu=0;
    FSCK_CACHE_CLUSTER_CHAIN_S* pstChain = NULL;
    FSCK_FRAGMENT_S* pstFrag = NULL;

    pstChain = FSCK_CACHE_MinChain(&g_stAllocatedCluster);
    if(!pstChain)
    {
        FSTOOL_COMM_LOG_ERROR("%s:g_stAllocatedCluster tree is empty\n",__func__);
        return FSCK_FSFATAL;
    }

    while (pstChain)
    {
        uUesdChainCnt++;
        uUsedSegmentCnt +=pstChain->segments;
        pstChain = FSCK_CACHE_NextChain(pstChain);
    }

    for (pstFrag = FSCK_FRAGMENT_Min(&g_stFreeCluster); NULL != pstFrag; pstFrag = FSCK_FRAGMENT_Next(pstFrag))
    {
        uFreeSegmentCnt++;
    }

    if (0 < uFreeSegmentCnt)
    {
        uFreeSegmentCnt--;
    }

    fVlu = (float)(uUsedSegmentCnt + uFreeSegmentCnt)/(float)(uUesdChainCnt+1);/*1 for free chain*/
    FSTOOL_COMM_LOG_INFO("total file cnt:%u, file segment cnt:%u, free segment cnt:%u, vlu:%f\n",uUesdChainCnt, uUsedSegmentCnt, uFreeSegmentCnt, fVlu);
    if (fVlu > u32FragmentThr)
    {
        FSTOOL_COMM_LOG_ERROR("fs fragment severly  \n");
        return  FSCK_FSFRAG;
    }

    return FSCK_FSOK;
}


